#include<iostream>
using namespace std;

template<class k>
struct menbers
{
	k _key;
	menbers<k>* _left;
	menbers<k>* _right;
	menbers(const k& key)
		:_left(nullptr)
		, _right(nullptr)
		, _key(key)
	{}
};

template<class k>
class SBTree
{
	typedef menbers<k> node;
public:
	bool insert(const k& key)
	{
		if (_root == nullptr)
		{
			_root = new node(key);
			return true;
		}
		node* cut = _root;
		node* parend = nullptr;

		while (cut)
		{
			parend = cut;
			if (cut->_key < key)
			{
				cut = cut->_right;
			}
			else if (cut->_key > key)
			{
				cut = cut->_left;
			}
			else
			{
				return false;
			}
		}
		cut = new node(key);
		if (parend->_key < key)
		{
			parend->_right = cut;
		}
		if (parend->_key > key)
		{
			parend->_left = cut;
		}
		return true;
	}
	void  _inorder(node* cut)
	{
		if (cut == nullptr)
		{
			return;
		}
		_inorder(cut->_left);
		cout << cut->_key << " ";
		_inorder(cut->_right);
		cout << endl;
	}
	void inorder()
	{
		_inorder(_root);
	}
private:
	node* _root = nullptr;
};